|
In compiler theory, loop dependence analysis is the task of determining whether statements within a loop body form a dependence, with respect to array access and modification, induction, reduction and private variables, simplification of loop-independent code and management of conditional branches inside the loop body. Loop dependence analysis is mostly done to find ways to do automatic parallelization, by means of automatic vectorization, shared memory or others. == Description == Loop dependence analysis occur on a normalized loop of the form: where ''body'' may contain:Where ''a'' is an m-dimensional array and fn, hn, etc. are functions mapping from all iteration indexes (in) to a memory access in a particular dimension of the array.For example, in C: for (i = 0; i < U1; i++) for (j = 0; j < U2; j++) a() = b() + i *j; f1 would be i+4-j, controlling the write on the first dimension of ''a'' and h2 would be 2, controlling the read on the first dimension of ''b''.The scope of the problem is to find all possible dependencies between ''S1'' and ''S2''. To be conservative, any dependence which cannot be proven false must be assumed to be true. Independence is shown by demonstrating that no two instances of ''S1'' and ''S2'' access or modify the same spot in array a. When a possible dependence is found, loop dependence analysis usually makes every attempt to characterize the relationship between dependent instances, as some optimizations may still be possible. It may also be possible to transform the loop to remove or modify the dependence.In the course of (dis)proving such dependencies, a statement ''S'' may be decomposed according to which iteration it comes from. For instance, ''S''() refers to the iteration where i1 = 1, i2 = 3 and i3 = 5. Of course, references to abstract iterations, such as ''S''(), are both permitted and common.抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Loop dependence analysis」の詳細全文を読む スポンサード リンク
|